package 力扣.动态规划;

//给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

public class 分割等和子集 {
    public static void main(String[] args) {
       int[] nums={1,5,11,5};
        boolean b = canPartition(nums);
        System.out.println(b);
    }
    public static boolean canPartition(int[] nums) {
        int N=nums.length;
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        //如果和是奇数，则不可能等分
        if (sum%2!=0)
            return false;
        sum=sum/2;
        //转换成0-1背包问题
        //初始化
        boolean[][] dp = new boolean[N + 1][sum+1];
        for (int i = 0; i <N+1; i++) {
            dp[i][0]=true;
        }
        for (int i = 1; i <N+1 ; i++) {
            for (int j = 1; j <sum+1 ; j++) {
                if (j<nums[i-1])
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]];
            }
        }
        return dp[N][sum];
    }
}
